"""
654. 最大二叉树 - 测试数据生成器

用于生成各种类型的测试数据，验证算法的正确性和性能
"""

import random
from typing import List, Tuple

class TestDataGenerator:
    """测试数据生成器"""
    
    def __init__(self, seed: int = 42):
        """初始化随机种子以确保可重现性"""
        random.seed(seed)
    
    def generate_basic_cases(self) -> List[Tuple[str, List[int]]]:
        """生成基本测试用例"""
        return [
            ("示例1", [3, 2, 1, 6, 0, 5]),
            ("示例2", [3, 2, 1]),
            ("单元素", [1]),
        ]
    
    def generate_boundary_cases(self) -> List[Tuple[str, List[int]]]:
        """生成边界测试用例"""
        return [
            ("递增序列", [1, 2, 3, 4, 5]),
            ("递减序列", [5, 4, 3, 2, 1]),
            ("最小长度", [0]),
            ("两元素递增", [1, 2]),
            ("两元素递减", [2, 1]),
        ]
    
    def generate_random_permutation(self, n: int) -> List[int]:
        """生成长度为n的随机排列"""
        nums = list(range(n))
        random.shuffle(nums)
        return nums
    
    def generate_max_at_position(self, n: int, max_pos: int) -> List[int]:
        """生成最大值在指定位置的数组"""
        if max_pos < 0 or max_pos >= n:
            raise ValueError(f"max_pos {max_pos} 超出范围 [0, {n-1}]")
        
        # 生成除最大值外的其他数字
        other_nums = list(range(n-1))
        random.shuffle(other_nums)
        
        # 将最大值插入指定位置
        result = other_nums[:max_pos] + [n-1] + other_nums[max_pos:]
        return result
    
    def generate_performance_cases(self) -> List[Tuple[str, List[int]]]:
        """生成性能测试用例"""
        cases = []
        
        # 不同规模的随机数组
        for size in [10, 50, 100, 500, 1000]:
            nums = self.generate_random_permutation(size)
            cases.append((f"随机数组_{size}", nums))
        
        # 最大值在不同位置的测试
        n = 100
        for pos_ratio in [0, 0.25, 0.5, 0.75, 1.0]:
            pos = int(pos_ratio * (n - 1))
            nums = self.generate_max_at_position(n, pos)
            cases.append((f"最大值在位置{pos_ratio*100:.0f}%", nums))
        
        # 最坏情况：递减序列（对递归法最不友好）
        for size in [10, 50, 100]:
            nums = list(range(size, 0, -1))
            cases.append((f"递减序列_{size}", nums))
        
        return cases
    
    def generate_special_cases(self) -> List[Tuple[str, List[int]]]:
        """生成特殊结构的测试用例"""
        return [
            ("V形", [1, 0, 2]),
            ("山形", [0, 3, 1, 2]),
            ("波浪形", [1, 3, 0, 5, 2, 4]),
            ("左偏树", [5, 4, 3, 2, 1, 0]),
            ("右偏树", [0, 1, 2, 3, 4, 5]),
        ]
    
    def generate_all_test_cases(self) -> List[Tuple[str, List[int]]]:
        """生成所有测试用例"""
        all_cases = []
        
        all_cases.extend(self.generate_basic_cases())
        all_cases.extend(self.generate_boundary_cases())
        all_cases.extend(self.generate_special_cases())
        all_cases.extend(self.generate_performance_cases())
        
        return all_cases
    
    def save_test_cases_to_file(self, filename: str = "test_cases.txt"):
        """将测试用例保存到文件"""
        cases = self.generate_all_test_cases()
        
        with open(filename, 'w', encoding='utf-8') as f:
            f.write("# 654. 最大二叉树 - 测试用例\n\n")
            
            for i, (name, nums) in enumerate(cases, 1):
                f.write(f"## 测试用例 {i}: {name}\n")
                f.write(f"输入: {nums}\n")
                f.write(f"长度: {len(nums)}\n\n")
        
        print(f"测试用例已保存到 {filename}")
        print(f"共生成 {len(cases)} 个测试用例")

def analyze_array_properties(nums: List[int]) -> dict:
    """分析数组的性质"""
    n = len(nums)
    if n == 0:
        return {"length": 0}
    
    max_val = max(nums)
    max_idx = nums.index(max_val)
    
    # 分析单调性
    is_increasing = all(nums[i] <= nums[i+1] for i in range(n-1))
    is_decreasing = all(nums[i] >= nums[i+1] for i in range(n-1))
    
    return {
        "length": n,
        "max_value": max_val,
        "max_position": max_idx,
        "max_position_ratio": max_idx / (n - 1) if n > 1 else 0,
        "is_increasing": is_increasing,
        "is_decreasing": is_decreasing,
        "left_subarray_length": max_idx,
        "right_subarray_length": n - max_idx - 1,
    }

def print_array_analysis(name: str, nums: List[int]):
    """打印数组分析结果"""
    props = analyze_array_properties(nums)
    print(f"\n=== {name} ===")
    print(f"数组: {nums}")
    print(f"长度: {props['length']}")
    if props['length'] > 0:
        print(f"最大值: {props['max_value']} (位置: {props['max_position']})")
        print(f"最大值位置比例: {props['max_position_ratio']:.2f}")
        print(f"左子数组长度: {props['left_subarray_length']}")
        print(f"右子数组长度: {props['right_subarray_length']}")
        print(f"递增序列: {props['is_increasing']}")
        print(f"递减序列: {props['is_decreasing']}")

def main():
    """主函数 - 生成并分析测试数据"""
    print("654. 最大二叉树 - 测试数据生成器")
    print("=" * 50)
    
    generator = TestDataGenerator()
    
    # 生成基本测试用例
    print("\n基本测试用例:")
    basic_cases = generator.generate_basic_cases()
    for name, nums in basic_cases:
        print_array_analysis(name, nums)
    
    # 生成边界测试用例
    print("\n边界测试用例:")
    boundary_cases = generator.generate_boundary_cases()
    for name, nums in boundary_cases:
        print_array_analysis(name, nums)
    
    # 生成特殊测试用例
    print("\n特殊测试用例:")
    special_cases = generator.generate_special_cases()
    for name, nums in special_cases:
        print_array_analysis(name, nums)
    
    # 保存所有测试用例到文件
    generator.save_test_cases_to_file()
    
    # 生成一些随机测试用例进行快速验证
    print("\n随机测试用例示例:")
    for i in range(3):
        size = random.randint(5, 10)
        nums = generator.generate_random_permutation(size)
        print_array_analysis(f"随机用例{i+1}", nums)

if __name__ == "__main__":
    main()